/*
 * 回溯法的 C 语言实现
 * build by: gcc algo.c
 * run by:   ./a.out
 * output:
 * Best positions: [0 5 4 1 2 3 ]
 * min cost: 174.000000
 */
#include<stdio.h>

typedef enum {
	false, true
} bool;

#define M 6  /* row count */
#define N 6  /* column count */

float m[] = {
	32, 24.5, 52, 45.5, 23, 63,
	34, 62.6, 39, 22, 34.5, 57,
	37.5, 61, 55, 43, 26, 41.5,
	43, 56, 38.5, 44, 53.5, 21,
	36, 27, 38, 42, 58, 64,
	46.5, 35, 47, 53, 35.5, 59.5,
};

int positions[N] = {0};
int best_positions[N] = {0};
float min_cost = 100000;

bool ok(int r, int c, float cost) {
	int i;
	for (i = 0; i < c; i++) {
		if (positions[i] == r) {
			return false;
		}
	}
	return cost + m[r*N+c] < min_cost;
}

void update_best_position() {
	int i;
	for (i = 0; i < N; ++i) {
		best_positions[i] = positions[i];
	}
}

void next_col(int c, float cost) {
	int r;
	if (c == N) {
		if (cost < min_cost) {
			min_cost = cost;
			update_best_position();
		}
		return;
	}
	for (r = 0; r < M; ++r) {
		if (ok(r, c, cost)) {
			positions[c] = r;
			next_col(c+1, cost + m[r*N+c]);
		}
	}
}

int main() {
	int i;
	next_col(0, 0);

	printf("Best positions: [");
	for (i = 0; i < N; i++) {
		printf("%d ", best_positions[i]);
	}
	printf("]\n");
	printf("min cost: %f\n", min_cost);
	return 0;
}
